#include <iostream>
#include <vector>
using namespace std;
class Solution {
 public:
  vector<int> path;
  vector<vector<int>> res;
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    int len = nums.size();
    vector<bool> used(len, false);
    sort(nums.begin(), nums.end());
    backtracking(nums, used, len);
    return res;
  }
  void backtracking(vector<int>& nums, vector<bool>& used, int len) {
    if (len == path.size()) {
      res.push_back(path);
      return;
    }
    for (int i = 0; i < len; i++) {
      // used[i - 1] == true，说明同一树支nums[i - 1]使用过
      // used[i - 1] == false，说明同一树层nums[i - 1]使用过
      // 如果同一树层nums[i - 1]使用过则直接跳过
      if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
        continue;
      }
      if (used[i] == false) {
        used[i] = true;
        path.push_back(nums[i]);
        backtracking(nums, used, len);
        path.pop_back();
        used[i] = false;
      }
    }
  }
};

/*
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int len = nums.size();
        vector<bool> used(len, false);
        sort(nums.begin(), nums.end());
        backtracking(nums, used, len);
        return res;
    }
    void backtracking(vector<int>& nums, vector<bool>& used, int len) {
        if(len == path.size()) {
            res.push_back(path);
            return ;
        }
        std::unordered_set<int> st;  // *
        for(int i = 0; i < len; i++) {
            if (st.find(nums[i]) != st.end()) {  // *
                continue;
            }
            if (used[i] == false) {
                st.insert(nums[i]);  // *
                used[i]=true;
                path.push_back(nums[i]);
                backtracking(nums, used, len);
                path.pop_back();
                used[i]=false;
            }

        }
    }
};
*/